/* eslint-disable no-console */
/* eslint-disable no-param-reassign */
import { exchange, randomInt } from './common'

/**
 * 使用数组区间中最后一个元素作为标准值，把数组分成前后两个部分。
 * 第一个部分包含所有小于等于标准值的元素。
 * 第二个部分包含所有大于标准值的元素。
 * 返回第一个部分最后一个元素的索引，也就是标准值最后的位置。
 * @param A the array
 * @param first the section first index
 * @param last the section last index
 * @returns the position of the standard value which is the last value of the input array
 */
export function partition(A: number[], first: number, last: number): number {
	const lastValue = A[last]
	let i = first - 1

	// 把区间中（包括最后一个）小于等于最后一个值的元素，前移到头部
	for (let j = first; j < last; j += 1) {
		if (A[j] <= lastValue) {
			i += 1
			exchange(A, i, j)
		}
	}
	// 前移最后一个元素
	exchange(A, i + 1, last)

	// 返回大于最后一个值的索引
	return i + 1
}

export function quickSort(A: number[], first: number, last: number): number[] {
	if (first < last) {
		const q: number = partition(A, first, last)
		quickSort(A, first, q - 1)
		quickSort(A, q + 1, last)
	}
	return A
}

export function randomizedPartition(A: number[], first: number, last: number): number {
	const i = randomInt(first, last)
	exchange(A, last, i)
	return partition(A, first, last)
}

export function randomizedQuickSort(A: number[], first: number, last: number): number[] {
	if (first < last) {
		const q: number = randomizedPartition(A, first, last)
		randomizedQuickSort(A, first, q - 1)
		randomizedQuickSort(A, q + 1, last)
	}
	return A
}

console.log(quickSort([7, 6, 5, 4, 3, 2, 1], 0, 6))
